package SortSummary;

/*
*   归并排序
*       归并排序是将整个数组分成一个个小数组，让这些小数组有序来实现整体有序
*       排序规则：
*           1.
*       时间复杂度：O(nlogn)
*       空间复杂度：
*       稳定性：稳定
* */

class MergerSort {
    //nums是要排序的数组，left-right是要排序的范围
    static void mergerSort(int[] nums,int left,int right){
        if(left == right){
            return;
        }
        int mid = left + ((right-left)>>1);
        mergerSort(nums,left,mid);
        mergerSort(nums,mid+1,right);
        merger(nums,left,mid,right);
    }
    private static void merger(int[] nums,int left,int mid,int right){
        int[] tempNums = new int[right-left+1];//保存排序后的数据
        int pt = 0;//临时数组指针
        int pl = left;//左边数组指针
        int pr = mid+1;//右边数组指针
        while(pl<=mid && pr<=right){
            tempNums[pt++] = nums[pl]>nums[pr]?nums[pr++]:nums[pl++];
        }
        while(pl<=mid){
            tempNums[pt++] = nums[pl++];
        }
        while(pr<=right){
            tempNums[pt++] = nums[pr++];
        }
        pt = 0;
        pl = left;
        while(pt<tempNums.length){
            nums[pl++] = tempNums[pt++];
        }
    }
}
